// https://leetcode.cn/problems/maximum-product-subarray/description/

// 算法思路总结：
// 1. 使用动态规划维护最大乘积和最小乘积
// 2. 由于负数存在，需要同时记录最大和最小值
// 3. 状态转移考虑当前值、当前值×最大值、当前值×最小值
// 4. 时间复杂度：O(n)，空间复杂度：O(n)

#include <iostream>
using namespace std;

#include <vector>
#include <algorithm>

class Solution 
{
public:
    int maxProduct(vector<int>& nums) 
    {
        int m = nums.size();
        int ret = -0x3f3f3f3f;

        vector<int> f(m + 1, 1), g(m + 1, 1);
        for (int i = 1 ; i <= m ; i++)
        {
            f[i] = max({nums[i - 1], f[i - 1] * nums[i - 1], g[i - 1] * nums[i - 1]});
            g[i] = min({nums[i - 1], f[i - 1] * nums[i - 1], g[i - 1] * nums[i - 1]});
            ret = max(ret, f[i]);
        }

        return ret;
    }
};

int main()
{
    vector<int> v1 = {2,3,-2,4}, v2 = {-2,0,-1};
    Solution sol;

    cout << sol.maxProduct(v1) << endl;
    cout << sol.maxProduct(v2) << endl;

    return 0;
}